package com.jay.structure;

/**
 * Created by caoyuan7 on 2018/11/30.
 */
public class Sort{

    private int [] array;

    public Sort(int [] array){
        this.array = array;
    }

    //按顺序打印数组中的元素
    public void display(){
        for(int i=0;i<array.length;i++){
            System.out.print(array[i]+"\t");
        }
        System.out.println();
    }

    //冒泡排序
    public void bubbleSort(){
        int temp;
        int len = array.length;

        for(int i=0;i<len-1;i++){  //外层循环：每循环一次就确定了一个相对最大元素 n
            for(int j=1;j<len-i;j++){  //内层循环：有i个元素已经排好，根据i确定本次的比较次数
                if(array[j-1]>array[j]){  //如果前一位大于后一位，交换位置
                    temp = array[j-1];
                    array[j-1] = array[j];
                    array[j] = temp;
                }
            }
            System.out.print("第"+(i+1)+"轮排序结果：");
            display();
        }
    }
    //选择排序
    public void selectionSort(){
        int minPoint;  //存储最小元素的小标
        int len = array.length;
        int temp;
        int counter = 1;

        for(int i=0;i<len-1;i++){

            minPoint= i;
            for(int j=i+1;j<=len-1;j++){  //每完成一轮排序，就确定了一个相对最小元素，下一轮排序只对后面的元素排序
                if(array[j]<array[minPoint]){  //如果待排数组中的某个元素比当前元素小，minPoint指向该元素的下标
                    minPoint= j;
                }
            }

            if(minPoint!=i){  //如果发现了更小的元素，交换位置
                temp= array[i];
                array[i]= array[minPoint];
                array[minPoint]= temp;
            }

            System.out.print("第"+counter+"轮排序结果：");
            display();
            counter++;
        }
    }
    //插入排序
    public void insertionSort(){

        int len = array.length;
        int counter = 1;

        for(int i=1;i<len;i++){
            int temp = array[i];  //存储待排序的元素值
            int insertPoint = i-1;  //与待排序元素值作比较的元素的下标

            while(insertPoint>=0 && array[insertPoint]>temp){ //当前元素比待排序元素大
                array[insertPoint+1] = array[insertPoint];  //当前元素后移一位
                insertPoint--;
            }

            array[insertPoint+1]= temp;  //找到了插入位置，插入待排序元素

            System.out.print("第"+counter+"轮排序结果：");
            display();
            counter++;
        }
//        i= 6 i<7
//        temp = 18
//        insertPoint = 5
//        1,2,4,5,11,18,20
    }

    public static void main(String args[]){
        int [] a = {1,5,4,11,2,20,18};
        Sort sort = new Sort(a);
        System.out.print("未排序时的结果：");
        sort.display();
        //sort.bubbleSort();
        //sort.selectionSort();
        sort.insertionSort();
    }
}
//i=0 j<7
//1,4,5,2,11,18,20
//
//i=1 j<6
//1,4,5,2,11,18,20
//
//i=2 j<5
//1,4,2,5,11,18,20